#ifndef _leftist_heap_h
#define _leftist_heap_h

#include<iostream>
#include<map>
// #include "priority_queue.h"
#include<vector>
using namespace std;

template <typename Unique, typename Comparable>
struct Data
{        
    Unique k;
    Comparable d;
    Data(Unique key, Comparable data):k(key), d(data){}
    Data(const Data& d):k(d.k), d(d.d){}
    Data(const Data&& d):k(std::move(d).k), d(std::move(d).d){}
    void operator=(const Data& data){k = data.k; d = data.d;}
};

template <typename Unique, typename Comparable>
struct LeftistNode
{
    static std::map<Unique, LeftistNode* > hashTable;
    Data<Unique, Comparable> data;
    LeftistNode *left;
    LeftistNode *right;
    LeftistNode *back = nullptr;
    static int count;
    int npl;
    LeftistNode(const Data<Unique, Comparable>& d, LeftistNode *lt = nullptr,
     LeftistNode *rt = nullptr, int np=0)
        :data(d), left{lt}, right{rt}, npl{np} 
        {   
            // std::cout << "Table Size: " << hashTable.size() << std::endl;
            // std::cout << "Now We have " << ++count << " nodes." << std::endl;
            count++;
            hashTable[data.k] = this;   }

    LeftistNode(const Data<Unique, Comparable>&& d, LeftistNode *lt = nullptr,
     LeftistNode *rt = nullptr, int np=0)
        :data(std::move(d)), left{lt}, right{rt}, npl{np} 
        {   
            // std::cout << "Table Size: " << hashTable.size() << std::endl;
            // std::cout << "Now We have " << ++count << " nodes." << std::endl;
            count++;
            hashTable[data.k] = this;    }

    ~LeftistNode()
    {
        hashTable.erase(data.k);
        // if(--count==0){
        //     cout << endl;
        //     std::cout << "Table Size: " << hashTable.size() << std::endl;
        //     std::cout << "Now We have " << count << " nodes." << std::endl;
        // }
    }

    void describe()
    {
        if(this != nullptr)
        {
            std::cout << this->data.d << '\t';
            this->left->describe();
            this->right->describe();
        }
    }
};

template <typename Unique, typename Comparable>
std::map<Unique, LeftistNode<Unique, Comparable>* > LeftistNode<Unique, Comparable>::hashTable;

template <typename Unique, typename Comparable>
int LeftistNode<Unique, Comparable>::count = 0;

template <typename Unique, typename Comparable>
class LeftistHeap
{
private:
    LeftistNode<Unique, Comparable> *root;

    void percolateDown(LeftistNode<Unique, Comparable> *node);
    static LeftistNode<Unique, Comparable>* merge(LeftistNode<Unique, Comparable>* h1, LeftistNode<Unique, Comparable>* h2)
    {
        if(h1 == nullptr && h2!=nullptr)
        {
            h2->back = nullptr;
            return h2;
        }
        if(h2 == nullptr && h1!=nullptr)
        {
            h1->back = nullptr;
            return h1;
        }
        if(h1 == nullptr && h2==nullptr)
            return nullptr;
        if(h1->data.d <= h2->data.d)
            return node_merge(h1, h2);
        else
            return node_merge(h2, h1);
    }

    static LeftistNode<Unique, Comparable>* node_merge(LeftistNode<Unique, Comparable>* min_root, LeftistNode<Unique, Comparable>* max_root)
    {
        min_root->back = nullptr;
        max_root->back = nullptr;
        if (min_root->left == nullptr)
        {
            min_root->left = max_root;
            max_root->back = min_root;
        }
        else
        {
            min_root->right = merge(min_root->right, max_root);
            min_root->right->back = min_root;
            if(min_root->left->npl < min_root->right->npl)
                swapChildren(min_root);
            min_root->npl = min_root->right->npl+1;
        }
        return min_root;
    }

    static void swapChildren(LeftistNode<Unique, Comparable>* h)
    {
        LeftistNode<Unique, Comparable>* p = h->left;
        h->left = h->right;
        h->right = p;
    }
    void makeEmpty(LeftistNode<Unique, Comparable>*& root);


public:
    LeftistHeap();
    LeftistHeap(LeftistHeap&);
    LeftistHeap(LeftistHeap&&);

    ~LeftistHeap();

    void insert(Data<Unique, Comparable>& _x);
    void insert(Data<Unique, Comparable>&& _x);
    void deleteMin();
    void buildHeap(const std::vector<Data<Unique, Comparable> >& _input);
    void remove(Unique k);
    void modifyData(Unique k, Comparable d);
    static void merge(LeftistHeap& _H1, LeftistHeap& _H2);
    void makeEmpty();
    LeftistHeap& operator=(LeftistHeap& _H);
    void describe();
    void rightExchange(LeftistNode<Unique, Comparable>*);
    void leftExchange(LeftistNode<Unique, Comparable>*);
    void makeLeftist(LeftistNode<Unique, Comparable>* root);
    void makeLeftist();
    void splay(LeftistNode<Unique, Comparable>* p);

};

template <typename Unique, typename Comparable>
LeftistHeap<Unique, Comparable>::LeftistHeap():root(nullptr){}

template <typename Unique, typename Comparable>
LeftistHeap<Unique, Comparable>::~LeftistHeap()
{
    this->makeEmpty();
    delete root;
    root = nullptr;
}

// makeEmpty Internal Interface
template <typename Unique, typename Comparable>
void LeftistHeap<Unique, Comparable>::makeEmpty(LeftistNode<Unique, Comparable>*& root)
{
    if(root!=nullptr)
    {
        makeEmpty(root->left);
        makeEmpty(root->right);
        delete root;
    }
    root = nullptr;
}

// makeEmpty public inteface
template <typename Unique, typename Comparable>
void LeftistHeap<Unique, Comparable>::makeEmpty()
{
    makeEmpty(root);
}

// Copy constructor deepcopy
template <typename Unique, typename Comparable>
LeftistHeap<Unique, Comparable>::LeftistHeap(LeftistHeap& _H)
{
    this->makeEmpty();
    root = _H.root;
    _H.root = nullptr;
}

template <typename Unique, typename Comparable>
LeftistHeap<Unique, Comparable>::LeftistHeap(LeftistHeap&& _H)
{
    this->makeEmpty();
    root = std::move(_H.root);
    _H.root = nullptr;
}

template <typename Unique, typename Comparable>
LeftistHeap<Unique, Comparable>& LeftistHeap<Unique, Comparable>::operator=(LeftistHeap& _H)
{
    this->makeEmpty();
    this->root = _H.root;
    _H.root = nullptr;
    return *this;
}

// static merge, return LeftistHeap&, only _H1 remained!
template <typename Unique, typename Comparable>
void LeftistHeap<Unique, Comparable>::merge(LeftistHeap<Unique, Comparable>& _H1, LeftistHeap<Unique, Comparable>& _H2)
{
    if(&_H1 != &_H2) // Avoid self-referenced merging
    {
        if(_H1.root == nullptr)
            _H1 = _H2;
        else
        {
            _H1.root = merge(_H1.root, _H2.root);
            _H2.root = nullptr;
        }
    }else
    {
        std::cout << "Self merge is forbidden" << std::endl;
    }
}

template <typename Unique, typename Comparable>
void LeftistHeap<Unique, Comparable>::insert(Data<Unique, Comparable>& _x)
{
    root = merge(new LeftistNode<Unique, Comparable>(_x), root);
}

template <typename Unique, typename Comparable>
void LeftistHeap<Unique, Comparable>::insert(Data<Unique, Comparable>&& _x)
{
    root = merge(new LeftistNode<Unique, Comparable>(std::move(_x)), root);
}

template <typename Unique, typename Comparable>
void LeftistHeap<Unique, Comparable>::describe()
{
    if(root == nullptr)
        std::cout << "This LeftistHeap is Empty!!" << std::endl;
    else
        root->describe();
}

template <typename Unique, typename Comparable>
void LeftistHeap<Unique, Comparable>::deleteMin()
{
    if(root == nullptr)
        std::cout << "It's Empty!" << std::endl;
    else
    {
        LeftistNode<Unique, Comparable>* oldroot = root;
        root = merge(root->left, root->right);
        delete oldroot;
        oldroot = nullptr;
    }
}

template <typename Unique, typename Comparable>
void LeftistHeap<Unique, Comparable>::buildHeap(const std::vector<Data<Unique, Comparable> >& _input)
{
    makeEmpty();
    auto iter = _input.begin();
    for(; iter!=_input.end(); ++iter)
    {
        root = merge(root, new LeftistNode<Unique, Comparable>(*iter));
    }
}

template <typename Unique, typename Comparable>
void LeftistHeap<Unique, Comparable>::splay(LeftistNode<Unique, Comparable>* p)
{
    if(p->left == nullptr)
        swapChildren(p);
    p->npl = 0;
    while(p->back != nullptr)
    {
        if(p->back->right == nullptr)
            break;
        else if(p->back->left->npl >= p->back->right->npl && p->back->npl == p->back->right->npl+1)
            break;
        else if(p->back->left->npl < p->back->right->npl)
            swapChildren(p->back);
        p->back->npl = p->back->right->npl+1;
        p = p->back;
    }
}

// logN 
template <typename Unique, typename Comparable>
void LeftistHeap<Unique, Comparable>::remove(Unique k)
{
    int i = LeftistNode<Unique, Comparable>::hashTable.count(k);
    if(LeftistNode<Unique, Comparable>::hashTable[k] == root)
    {
        deleteMin();
    }
    else if(i == 1)
    {
        
        LeftistNode<Unique, Comparable>* p = LeftistNode<Unique, Comparable>::hashTable[k];
        LeftistNode<Unique, Comparable>* _root = p;
        if(p->back->right == p)
        {
            p = p->back;
            p->right->back = nullptr;
            p->right = nullptr;
            //splay
            splay(p);
        }
        else if(p->back->left == p)
        {
            p = p->back;
            p->left->back = nullptr;
            p->left = nullptr;
            //splay
            splay(p);
        }
        auto oldroot = _root;
        _root = merge(_root->left, _root->right);
        delete oldroot;
        oldroot = nullptr;
        root = merge(root, _root);
    }else
    {
        std::cout << "The element is not present in this leftist heap!" << std::endl;
    }
}

// Method 2
template <typename Unique, typename Comparable>
void LeftistHeap<Unique, Comparable>::modifyData(Unique k, Comparable d)
{
    if(LeftistNode<Unique, Comparable>::hashTable.count(k) == 0)
        std::cout << "The element is not present in this leftist heap!" << std::endl;
    else
    {
        LeftistNode<Unique, Comparable>* ind = LeftistNode<Unique, Comparable>::hashTable[k];
        ind->data.d += d;
        auto temp = Data<Unique, Comparable>(ind->data);
        if((ind->left!=nullptr && ind->data.d > ind->left->data.d)
          || (ind->right != nullptr && ind->data.d > ind->right->data.d)
          || (ind->back != nullptr && ind->data.d < ind->back->data.d ))
        {
            remove(ind->data.k);            
            root = merge(root, new LeftistNode<Unique, Comparable>(temp));
        }
    }
}

#endif // !_leftist_heap_h